//给你两个字符串 start 和 target ，长度均为 n 。每个字符串 仅 由字符 'L'、'R' 和 '_' 组成，其中： 
//
// 
// 字符 'L' 和 'R' 表示片段，其中片段 'L' 只有在其左侧直接存在一个 空位 时才能向 左 移动，而片段 'R' 只有在其右侧直接存在一个 空位 
//时才能向 右 移动。 
// 字符 '_' 表示可以被 任意 'L' 或 'R' 片段占据的空位。 
// 
//
// 如果在移动字符串 start 中的片段任意次之后可以得到字符串 target ，返回 true ；否则，返回 false 。 
//
// 
//
// 示例 1： 
//
// 输入：start = "_L__R__R_", target = "L______RR"
//输出：true
//解释：可以从字符串 start 获得 target ，需要进行下面的移动：
//- 将第一个片段向左移动一步，字符串现在变为 "L___R__R_" 。
//- 将最后一个片段向右移动一步，字符串现在变为 "L___R___R" 。
//- 将第二个片段向右移动散步，字符串现在变为 "L______RR" 。
//可以从字符串 start 得到 target ，所以返回 true 。
// 
//
// 示例 2： 
//
// 输入：start = "R_L_", target = "__LR"
//输出：false
//解释：字符串 start 中的 'R' 片段可以向右移动一步得到 "_RL_" 。
//但是，在这一步之后，不存在可以移动的片段，所以无法从字符串 start 得到 target 。
// 
//
// 示例 3： 
//
// 输入：start = "_R", target = "R_"
//输出：false
//解释：字符串 start 中的片段只能向右移动，所以无法从字符串 start 得到 target 。 
//
// 
//
// 提示： 
//
// 
// n == start.length == target.length 
// 1 <= n <= 10⁵ 
// start 和 target 由字符 'L'、'R' 和 '_' 组成 
// 
//
// Related Topics 双指针 字符串 👍 39 👎 0


package LeetCode.editor.cn;

/**
 * @author ldltd
 * @date 2023-08-21 01:42:20
 * @description 2337.移动片段得到字符串
 */
public class MovePiecesToObtainAString{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new MovePiecesToObtainAString().new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 /*时间on，空间o1
		 * 不能由 start 变成 target 一共有三种情况：
去掉 空格('_') 后，start 和 target 不等；
start L 左侧空格数小于 target L 左侧空格数；
start R 右侧空格数小于 target R 右侧空格数。*/
    public boolean canChange(String start, String target) {
			int n=start.length(),i=0,j=0;
		while (i<n&&j<n){
			/*先两个字符串，都移动到L或R*/
			while (i<n&&start.charAt(i)=='_'){
				i++;
			}
			while (j<n&&target.charAt(j)=='_'){
				j++;
			}
			//如果不相等，直接为false
			if(i<n&&j<n){
				if(start.charAt(i)!=target.charAt(j)){
					return false;
				}
				char c = start.charAt(i);
				//如果为L且，i<j，此时，L不能右移，false，同理R
				if((c=='L'&&i<j)||(c=='R'&&i>j)){
					return false;
				}
				i++;
				j++;
			}
		}
		//其中一个循环完了，如果另一个剩下的不是’_‘，则false
		while (i<n){
			if (start.charAt(i) != '_') {
				return false;
			}
			i++;
		}
		while (j<n){
			if (target.charAt(j) != '_') {
				return false;
			}
		j++;
	}
		return true;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
